Large scale networks require switches that can handle traffic from many customers. Telephony was an early example.
C. Clos showed that a switching machine which routes traffic between thousands of telephone lines can be constructed by assembling a network of small switches. Clos used analog switch nodes constructed from relays. For more information, see Charles Clos, “A Study of Non-Blocking Switching Networks”, Bell System Technical Journal, Vol. 32, pages 406-424, 1953.
With the advent of computer communication, D. Wheeler and A. Hopper described how a large packet switch might be constructed from a network of digital switch nodes with embedded memory. For more information, see A. Hopper and D. J. Wheeler “Binary Routing Networks” IEEE Trans. on Computers, Vol C-28,10 p 699-703 (October 1979).
Memory is required to hold packets which find their way blocked by another packet that is using the same path in the network. It was soon found that some traffic patterns generate “hot spots” in the network—places where a high concentration of traffic leads to delay and/or cell loss. This problem can be eased by enlarging the network so that it offers a choice of paths between ingress and egress ports, then by adding a degree of randomness to the way that traffic is routed, hot spots are dispersed. However, random routing can cause cells to be delivered out of sequence. It also helps to operate the network at a speed that is higher than the combined speed of the switch ingress ports, but power consumption and mechanical design are problematic for large switches.
In the years to come broadband packet switched communication will likely be made available to homes and businesses throughout the United States. Transmission rates available to ordinary consumers are likely to be at least 100 Mb/sec. In order to deliver this service on a massive scale it may be necessary to create a new national communications infrastructure. Economy and large scale will dictate high performance regional networks each serving perhaps one million homes and a fiber-optic backbone network that connects to the regional networks through high capacity packet switches. Accordingly, there is a need for a packet switch that can operate with sufficient speed and on such a scale.
Additional information may be found at: V. E. Benes, “Mathematical Theory of Connecting Networks and Telephone Traffic”, Academic Press, 1965; Nick Mckeown, “The iSLIP Scheduling Algorithm for Input Queued Switches”, IEEE/ACM Transactions on Networking, (April 1999); P. Krishna, N. Patel, A. Charny and R. Simcoe “On the speedup required for work-conserving crossbar switches”, IEEE J. Selected Areas of Communications, (June 1999); C. Minkenberg, R. P. Luijten, F. Abel, W. Denzel and M. Gusat, “Current Issues in Packet Switch Design”, Hotenets '02 conf.proc., Princeton, N.J., (October 2002); Hemant R. Kanakia, “High-Speed Packet Switch”, U.S. Pat. No. 5,309,432, May 1994; “IDT 77v400 and IDT77v500 SWITCHStAR User's Manual” Integrated Device Technologies, 2975 Stender Way, Santa Clara, Calif. 95054, March 1999, and; Shang-Tse Chuang, Ashish Goel, Nick McKeown and Balaji Prabhakar, “Matching Output Queuing with a Combined Input and Output Queued Switch”, Proceedings of Infocom, 1999.